концепция, дополняющая постулаты классической теории химического строения и утверждающая, что если для данного соединения классическая теория (см. Химического строения теория) допускает построение нескольких приемлемых (согласующихся с требованиями валентности) структурных формул, то действительному состоянию молекул этого соединения отвечает не какая-либо отдельная формула, а некоторое их сочетание (наложение).

Р. т. основана на представлениях, сложившихся в химии под влиянием результатов экспериментальных исследований, в которых была обнаружена недостаточность классической теории строения и расхождения этой теории с опытом, а также на идеях одного из квантовомеханических методов расчёта молекул - метода валентных схем, или валентных структур, в котором каждой классической структурной формуле (валентной схеме, или структуре) сопоставляется волновая функция, определённым образом построенная из атомных орбиталей, а волновая функция действительного состояния аппроксимируется линейной комбинацией функций отдельных структур (см. Квантовая химия, Валентность). Эти представления дополняются в Р. т. критериями отбора наиболее существенных структур среди всех возможных. Так, если в валентной схеме валентный штрих соединяет далеко расположенные друг от друга атомы, то такая схема будет менее значимой, чем та, в которой валентные штрихи соединяют только соседние атомы, и т. п. Для бензола наряду с двумя классическими эквивалентными формулами (структуры Кекуле)

можно записать формулы

(структуры Дьюара), в которых один из валентных штрихов соединяет несоседние атомы. Такие структуры должны играть при описании действительного состояния молекулы бензола меньшую роль, чем структуры Кекуле. Роль тех или иных структур определяется качественными следствиями вариационного принципа квантовой механики: для основного состояния наиболее существенны те структуры, энергия которых минимальна. Чем выше энергия данной структуры по сравнению с минимальной величиной энергии структур, тем менее существенна эта структура для описания молекулы в целом. Согласно вариационному принципу, энергия Е, вычисляемая с оптимальной линейной комбинацией волновых функций структур i меньше энергии E_i каждой отдельной структуры. Минимальное значение разности E_i - Е носит название энергии резонанса. Как правило, чем больше значение этой разности, тем больше отклоняется описание состояния реальной молекулы от описания, получаемого в рамках классической теории строения при использовании только одной структурной формулы. На практике обычно пользуются иной величиной, называемой экспериментальной энергией резонанса и определяемой как разность между экспериментальной теплотой образования соединения и энергией, вычисленной для одной структуры, отвечающей классической структурной формуле, при использовании табличных значений энергий отдельных связей.

Для описания молекул многих классов соединений достаточно ограничиться одной валентной структурой (например, молекулы насыщенных углеводородов). Для других молекул, например с сопряжённым двойными и тройными связями, приходится использовать представление о наложении (резонансе) нескольких валентных структур. В этих случаях Р. т. прибегает к совокупности структурных формул вместо какой-либо одной формулы, что отличает её от других способов описания, пользующихся пунктирными линиями для валентных штрихов, стрелками для указания смещений электронной плотности и т. п. Отдельные структуры при этом не представляют каких-либо независимых, реально существующих состояний молекулы и являются лишь составными элементами единого описания одного состояния, аналогично тому, как отдельные элементы классического описания (простые связи, двойные связи и т. д.) служат для единого описания структуры молекулы в целом.

Р. т. позволяет качественно или полуколичественно (путём простых вычислений на базе упрощённых вариантов метода валентных схем) судить о симметрии молекул, об эквивалентности тех или иных связей и структурных элементов в молекулах, о стабильности и реакционной способности молекул. Она помогает понять, а отчасти и предвидеть результаты экспериментальных исследований, не претендуя на большую строгость рассуждений и не опираясь на достаточно строгие, но громоздкие квантовомеханические расчёты. В рамках Р. т. были введены такие широко используемые в настоящее время представления, как одно- и трёх-электронные связи, гибридизация связевых орбиталей, сверхсопряжение, а также представление о частично ионном характере ковалентных связей между различными атомами (резонанс ковалентной и ионной структур).

Р. т. была предложена Л. Полингом в 1928-31 гг. и развита в последующие годы в основном в трудах его школы. Термин "резонанс" был заимствован у В. Гейзенберга, проследившего аналогию между квантовомеханическим описанием систем, например двух связанных осцилляторов, и их классическим описанием, учитывающим резонанс в такой системе.

Лит.: Паулинг Л., Природа химической связи, пер. с англ., М. - Л., 1947; Уэланд Д., Теория резонанса и её применение в органической химии, пер. с англ., М., 1948; Полинг Л., Теория резонанса в химии, "Журнал Всесоюзного химического общества им. Д. И. Менделеева", 1962, т. 7, № 4, с. 462; Pauling L., The nature of the chemical bond, 3 ed., lthaca - N. Y., 1960.

катастрофизм учение 1-й половины 19 в., рассматривавшее геологическую историю Земли как чередование длительных эпох относительного покоя и сравнительно коротких катастрофических событий, резко преображавших лик планеты. Идея о катастрофах зародившаяся в глубокой древности, в 17-18 вв. стала использоваться для истолкования геологической истории. Но т.к. длительность существования Земли до начала 19 в. оценивалась не более чем в 100 тыс. лет, было трудно объяснить действием обычных причин зафиксированные в толщах пород огромные изменения, претерпевавшиеся Землёй и её органическим миром в прошлом. Стремясь найти выход из этого затруднения, французский естествоиспытатель Ж. Кювье в 1812 выдвинул гипотезу о катастрофах (переворотах), во время которых на большей части планеты якобы погибало всё живое, а затем опустошённые места заселялись другими видами организмов, пережившими катастрофу в отдалённых районах. Это была попытка не только объяснить грандиозность прошлых преобразований Земли, но и преодолеть противоречие между господствовавшими убеждениями в неизменности видов и уже тогда прочно установленным фактом многократной смены в геологическом разрезе отличных друг от друга ископаемых флор и фаун. Идеи Кювье развивали французский палеонтолог А. д'Орбиньи, швейцарский геолог Л. Агассис, английский геолог А. Седжвик и др., насчитывавшие в геологической истории Земли 27 катастроф, во время которых якобы погибал весь органический мир. После каждой катастрофы, по представлениям этих учёных, в результате очередного божественного "акта творения" создавались совершенно новые растения и животные, не связанные с ранее существовавшими; каждый раз они были более сложно и совершенно организованы, чем предшествующие. В периоды между катастрофами никакого развития и изменений вновь созданные живые существа якобы не претерпевали. Концепция катастрофизма и неоднократных творческих актов согласовывалась с библейской версией творения мира. Принимая эту концепцию, можно было объяснить современное состояние поверхности Земли как результат последнего во времени творческого акта.

Тем не менее катастрофизм первой половины 19 в. сыграл положительную роль в развитии биостратиграфии (См. Биостратиграфия), поскольку учением о резких границах между различными по возрасту толщами и качественным своеобразием органического мира каждого периода (эпохи, века) он способствовал укреплению понятия о руководящих окаменелостях. Положительным было и то, что благодаря К. т. широко распространились идеи о прогрессе в органическом мире и об эпизодических событиях, нарушающих однообразие в истории Земли. Это способствовало формированию в дальнейшем представлений о сочетании эволюционного и скачкообразного развития. В середине 19 в. К. т. стала утрачивать своё значение в геологии благодаря победе представлений о том, что ныне действующих геологических факторов достаточно для осуществления за длительный срок всех перемен, зафиксированных в разрезе (Ч. Лайель). Позднее катастрофизм был побежден и в биологии в результате развития эволюционных представлений (Ч. Дарвином и др.). Однако отказ от идей катастрофизма не был окончательным: в 1-й половине 20 в. они частично возродились в форме так называемого неокатастрофизма - представления об одновременных на всей планете фазах складчатости и горообразования, прерывающих длительные эпохи относительного покоя и медленной эволюции коры (нем. геолог Х. Штилле и его последователи); высказываются мысли о катастрофических событиях во Вселенной, вызывающих усиленную радиацию, обусловливающую гибель одних групп организмов и быстрые мутационные изменения других, приводящие к возникновению новых видов и родов живых организмов (нем. палеонтолог О. Шиндевольф). Убедительная критика идей неокатастрофизма в тектонике дана Н. С. Шатским, а в палеонтологии - Л. Ш. Давиташвили.

В. В. Тихомиров.

раздел математики, изучающий кажущееся случайным или очень сложное поведение детерминированных динамических систем. Динамическая система - это такая система, состояние которой меняется во времени в соответствии с фиксированными математическими правилами; последние обычно задаются уравнениями, связывающими будущее состояние системы с текущим. Такая система детерминирована, если эти правила не включают явным образом элемента случайности.

Вплоть до 1960-х годов многим казалось естественным полагать, что динамическая система, описываемая простыми детерминистическими уравнениями, должна вести себя относительно просто, хотя уже более столетия было известно, что это верно лишь в некоторых весьма специальных случаях, таких, как Солнечная система. Однако к 1980 математики и естествоиспытатели обнаружили, что хаос вездесущ.

Пример хаотического поведения из повседневной жизни - движение жидкости в миксере. Это устройство подчиняется простым механическим законам: его нож-смеситель вращается с постоянной скоростью, и взаимодействие жидкости с ножом внутри миксера можно описать простыми детерминистическими уравнениями. Однако возникающее при этом движение жидкости весьма сложно. Ее соседние области рассекаются ножом и разделяются, а отдаленные области могут сближаться. Короче говоря, жидкость перемешивается - для этого миксеры и предназначены.

Выражение "теория хаоса" используется преимущественно в популярной литературе. Специалисты же рассматривают эту дисциплину как раздел теории динамических систем.

Основные принципы. Для изучения хаоса используют общие математические принципы и компьютерное моделирование. Фундаментальной характеристикой всякой динамической системы является итерация, т.е. результат повторного (многократного) применения одного и того же математического правила к некоторому выбранному состоянию. Состояние обычно описывается числом или набором чисел, но это может быть также геометрическая фигура или конфигурация. Например, пусть правилом будет "разделить на два". Начав с исходного состояния, задаваемого числом 1, это правило дает итерации 1/2, 1/4, 1/8,..., образующие очевидную закономерную последовательность. Правило "возвести в квадрат и вычесть единицу", примененное к 0, дает последовательность -1, 0, -1, 0,..., которая циклически и неограниченно скачет между числами 0 и ?1. Однако правило "возвести в квадрат, удвоить и затем вычесть единицу", если начать применять его, скажем, к значению 0,1, порождает последовательность чисел ?0,98, 0,92, 0,69, ?0,03,..., в которой не удается заметить никакой очевидной закономерности.

Основным понятием теории хаоса является аттрактор, т.е. то поведение, к которому в конце концов приходит или в пределе стремится система. Аттракторами для трех описанных выше систем являются: единственное число 0; пара чисел (0, ?1); весь интервал чисел между -1 и 1. Динамика в этих трех случаях соответственно стационарная, периодическая и хаотическая. Хаотический аттрактор обладает скрытой структурой, которая часто становится явной после графического представления итераций. Состояние динамической системы - это набор чисел, которые можно интерпретировать как координаты изображающей его точки в некотором фазовом пространстве. Когда состояние системы меняется, эта точка движется. Для стационарного аттрактора движущаяся точка стремится к фиксированному положению, а для периодического аттрактора она циклически проходит через фиксированную последовательность положений. В случае хаотического аттрактора движущаяся точка образует более сложную конфигурацию с очень хитроумной, многослойной структурой. Такие конфигурации называют фракталами; этот термин был введен в 1970 Б.Мандельбротом. Его работы впоследствии стимулировали огромное количество исследований по фрактальной геометрии.

Важной чертой хаотической динамики является ее непредсказуемость. Представим себе две частички порошка, находящиеся рядом друг с другом в жидкости внутри миксера. После включения миксера эти две частички недолго останутся рядом; они быстро разойдутся в разные стороны и вскоре начнут двигаться независимо. Подобным же образом, если дважды запустить хаотическую систему из очень близких начальных состояний, ее поведение в этих двух случаях быстро станет совершенно непохожим. Это означает, что на больших временных интервалах хаотические системы непредсказуемы. Малейшая погрешность измерения начального состояния быстро растет, и предсказание будущего состояния становится все более неточным. Однако, в отличие от случайной системы, краткосрочное прогнозирование здесь возможно.

История вопроса. Понятие хаоса не было в явном виде сформулировано до 1960-х годов, но его истоки можно проследить начиная с последнего десятилетия 19 в., когда появилась удостоенная премии работа французского математика А.Пуанкаре о движении в Солнечной системе. Двумя столетиями раньше Ньютон установил закон всемирного тяготения, из которого вывел, что движение двух притягивающихся тел в отсутствие других сил описывается просто: каждое из них перемещается относительно их общего центра масс по одному из конических сечений - окружности, эллипсу, параболе, гиперболе или прямой. Для трех или большего числа тел, однако, нельзя найти подобного простого решения, и Пуанкаре показал, что эта трудность вызвана не недостатком человеческой изобретательности, а свойствами, внутренне присущими динамике многих тел. Он установил, что даже в ограниченной задаче трех тел, масса одного из которых пренебрежимо мала, возможно столь сложное движение, что его нельзя описать никакой математической формулой. См. также НЕБЕСНАЯ МЕХАНИКА
.

В 1926-1927 голландский инженер Б.Ван-дер-Пол сконструировал электронную схему, соответствующую математической модели сердечных сокращений. Он обнаружил, что при определенных условиях возникающие в схеме колебания были не периодическими, как при нормальном сердцебиении, а нерегулярными. Его работа получила серьезное математическое обоснование в годы Второй мировой войны, когда Дж.Литтлвуд и М.Картрайт исследовали принципы радиолокации. В начале 1960-х годов американский математик С.Смейл попытался построить исчерпывающую классификацию типичных разновидностей поведения динамических систем. Поначалу он предполагал, что можно обойтись различными комбинациями периодических движений, но вскоре понял, что возможно значительно более сложное поведение. В частности, он подробнее исследовал открытое Пуанкаре сложное движение в ограниченной задаче трех тел, упростив геометрию и получив при этом систему, известную ныне как "подкова Смейла". Он доказал, что такая система, несмотря на ее детерминированность, проявляет некоторые черты случайного поведения. Другие примеры подобных явлений были разработаны американской и российской школами в теории динамических систем, причем особенно важным оказался вклад В.И.Арнольда. Так начала возникать общая теория хаоса. Сам термин "хаос" ввели Дж.Йорке и Т.Ли в 1975 в краткой статье, посвященной обсуждению некоторых результатов исследований российской школы.

Исследования хаотических систем время от времени появлялись и в литературе по прикладным вопросам. Наиболее известная из таких моделей была введена метеорологом Э.Лоренцем в 1963. Лоренц построил модель конвекции в атмосфере, создав приближения очень сложных уравнений, описывающих это явление, значительно более простыми уравнениями с тремя неизвестными. Численно решая их на компьютере, он обнаружил, что решения колеблются нерегулярным, почти случайным образом. Лоренц также установил, что если слегка изменять начальные значения переменных, то отклонения будут усиливаться, пока новое решение не окажется совершенно непохожим на исходное. Описание им этого явления в последующих лекциях привело к популярному ныне выражению "эффект бабочки": взмах крыла бабочки может изменить погоду.

Примеры приложений. Теория хаоса находит приложения в широком спектре наук. Одним из самых ранних стало ее применение к анализу турбулентности в жидкости. Движение жидкости бывает либо ламинарным (гладким и регулярным), либо турбулентным (сложным и нерегулярным). До появления теории хаоса существовали две конкурирующие теории турбулентности. Первая из них представляла турбулентность как накопление все новых и новых периодических движений; вторая объясняла неприменимость стандартной физической модели невозможностью описания жидкости как сплошной среды в молекулярных масштабах. В 1970 математики Д.Рюэль и Ф.Такенс предложили третью версию: турбулентность - это хаос в жидкости. Их предположение поначалу считалось весьма спорным, но с тех пор оно было подтверждено для нескольких случаев, в частности, для ранних стадий развития турбулентности в течении между двумя вращающимися цилиндрами. Развитая турбулентность по-прежнему остается загадочным явлением, но хаоса вряд ли удается избежать в любом возможном ее объяснении. См. также ГИДРОАЭРОМЕХАНИКА
.

Ранняя работа Э.Лоренца в области метеорологии получила дальнейшее развитие, и теперь известно, что полные уравнения поведения атмосферы, используемые при прогнозировании погоды, могут вести себя хаотически. Это означает, что долгосрочные прогнозы погоды на основе данных о ее прошлом состоянии подвержены "эффекту бабочки", так что погода обычно не может быть предсказана более чем на четыре или пять дней вперед - независимо от мощности используемых компьютеров.

Движение в Солнечной системе тоже, как известно, хаотично, но здесь требуются десятки миллионов лет, прежде чем какое-то изменение станет непредсказуемым. Хаос проявляет себя многообразными способами. Например, спутник Сатурна Гиперион обращается по регулярной, предсказуемой орбите вокруг своей планеты, но при этом он хаотически кувыркается, изменяя направление оси собственного вращения. Теория хаоса объясняет это кувыркание как побочное действие приливных сил, создаваемых Сатурном. Теория хаоса объясняет также распределение тел в поясе астероидов между Марсом и Юпитером. Оно неравномерно: на одних расстояниях от Солнца существуют сгущения, на других - пустые промежутки. И сгущения, и пустые промежутки их гелиоцентрических орбит находятся на расстояниях, образующих "резонансы" с Юпитером, т.е. период обращения каждого астероида составляет некую простую дробь с периодом обращения Юпитера. Например, в резонансе 2:3 период обращения астероида равен 2/3 периода обращения Юпитера. Теория хаоса показывает, что одни резонансы порождают устойчивое поведение (сгущения), тогда как другие - неустойчивое (пустые промежутки). В частности, астероиды в резонансе 1:3 с Юпитером имеют неустойчивые орбиты и могут испытать возмущения, заставляющие их пересечь орбиту Марса, после чего они могут испытать дальнейшие возмущения и пересечь орбиту Земли. В 1995 Ж.Ласкар установил, что на временных масштабах десятков миллионов лет вся Солнечная система хаотична. Однако хаос не делает все черты движения в Солнечной системе непредсказуемыми. Например, форма планетной орбиты может быть предсказуемой, однако точное положение планеты на орбите остается непредсказуемым. Ласкар предсказал вероятное будущее Солнечной системы в целом на следующие несколько миллиардов лет. Согласно его вычислениям, ничего существенного не случится с орбитами внешних планет - Юпитера, Сатурна, Урана, Нептуна и Плутона. Орбиты Земли и Венеры тоже не претерпели бы существенных изменений, если бы не Марс, орбита которого изменится настолько, что он едва не столкнется с Землей. Меркурий тоже приблизится к Венере и будет либо выброшен из Солнечной системы, либо поменяется местами с Венерой.

Хаос имеет место также в биологии и экологии. В конце 19 в. было установлено, что популяции животных редко бывают стабильными; им свойственны нерегулярно чередующиеся периоды быстрого роста и почти полного вымирания. Теория хаоса показывает, что простые законы изменения численности популяций могут объяснить эти флуктуации без введения случайных внешних воздействий. Теория хаоса также объясняет динамику эпидемий, т.е. флуктуирующих популяций микроорганизмов в организмах людей.

Может создаться впечатление, что теория хаоса не должна иметь каких-либо полезных применений, поскольку хаотические системы непредсказуемы. Однако это неверно, во-первых, потому, что лишь некоторые аспекты хаотических систем непредсказуемы, и, во-вторых, потому, что полезность теории не ограничивается способностью прямого прогнозирования. В частности, теория хаоса предлагает новые методы анализа данных и обнаружения скрытых закономерностей там, где прежде систему считали случайной и никаких закономерностей в ее поведении не искали, полагая, что их просто не существует. Одним из приложений этого подхода служит машина FRACMAT, обеспечивающая дешевую и быструю процедуру контроля качества пружинной проволоки.

К числу наиболее перспективных применений теории хаоса принадлежит "хаотическое управление". В 1950 Дж.фон Нейман предположил, что неустойчивость погоды может в один прекрасный день обернуться благом, поскольку неустойчивость означает, что желаемый эффект может быть достигнут очень малым возмущением. В 1990 С.Гребоджи, Э.Отт и Дж.Йорке опубликовали теоретическую схему использования этого вида неустойчивости для управления хаотическими системами. Их схема представляет собой общую форму того метода, с помощью которого в 1985 инженеры НАСА послали космический зонд на встречу с кометой Джакобини - Циннера. Зонд пять раз облетел Луну, используя хаотичность взаимодействия трех тел, позволяющую совершать большие изменения траектории с малыми затратами топлива. Тот же метод был применен для синхронизации батареи лазеров; для управления нерегулярностями сердцебиения, что открывает возможность создать "интеллектуальный" стимулятор сердечного ритма; для управления биотоками мозга, что, в частности, может помочь контролировать эпилептические припадки; наконец, для ламинаризации турбулентного течения жидкости - метод, который способен уменьшить расход топлива самолетами.

раздел математики, изучающий общие свойства Алгоритмов. Содержательные явления, приведшие к образованию понятия "алгоритм", прослеживаются в математике в течение всего времени её существования. Однако само это понятие сформировалось лишь в 20 в. и стало предметом самостоятельного изучения (по-видимому, впервые, хотя ещё в расплывчатом виде) лишь в 20-х гг. 20 в. в трудах представителей математического интуиционизма (См. Математический интуиционизм) Л. Э. Я. Брауэра и Г. Вейля (См. Вейль). Началом систематической разработки А. т. можно считать 1936, когда А. Чёрч опубликовал первое уточнение понятия вычислимой функции (См. Вычислимая функция)(предложив отождествлять понятие всюду определённой вычислимой функции, имеющей натуральные аргументы и значения, с понятием общерекурсивной функции) и привёл первый пример функции, не являющейся вычислимой, а А. М. Тьюринг и Э. Л. Пост дали первые уточнения понятия алгоритма (в терминах идеализированных вычислительных машин, см. Тьюринга машина). В дальнейшем А. т. получила развитие в трудах С. К. Клини, Э. Л. Поста, А. А. Маркова и других. В частности, А. А. Марков предложил уточнять понятие алгоритма с помощью введённого им понятия нормального алгоритма (См. Нормальный алгорифм). Наиболее общий подход к уточнению понятия алгоритма предложил А. Н. Колмогоров.

Основные понятия А. т. Областью применимости алгоритма называется совокупность тех объектов, к которым он применим. Про алгоритм ℑ говорят, что он: 1) "вычисляет функцию f", коль скоро его область применимости совпадает с областью определения f и ℑ перерабатывает всякий x из своей области применимости в f(x), 2) "разрешает множество А относительно множества X", коль скоро он применим ко всякому х из Х и перерабатывает всякий х из Х ∩ A в слово "да", а всякий х из ХA в слово "нет"; 3) "перечисляет множество В", коль скоро его область применимости есть натуральный ряд, а совокупность результатов есть В. Функция называется вычислимой, если существует вычисляющий её алгоритм. Множество называется разрешимым относительно X, если существует разрешающий его относительно Х алгоритм (см. Разрешимое множество). Множество называется перечислимым, если либо оно пусто, либо существует перечисляющий его алгоритм (см. Перечислимое множество).

Детальный анализ понятия "алгоритм" обнаруживает, что (I) область возможных исходных данных и область применимости любого алгоритма суть перечислимые множества. В свою очередь (II) для любой пары вложенных одно в другое перечислимых множеств можно подобрать алгоритм, у которого большее множество служит множеством исходных данных, а меньшее - областью применимости. Имеют место следующие основные теоремы: (III) функция f вычислима тогда и только тогда, когда перечислим её график, т. е. множество всех пар вида . (IV) Подмножество А перечислимого множества Х тогда и только тогда разрешимо относительно X, когда А и Х А перечислимы. (V) Если А и В перечислимы, то A' ∪B и А ∩В также перечислимы. (VI) В каждом бесконечном перечислимом множестве Х существует перечислимое подмножество с неперечислимым дополнением [в силу (IV) это перечислимое подмножество будет неразрешимым относительно X]. (VII) Для каждого бесконечного перечислимого множества Х существует вычислимая функция, определённая на подмножестве этого множества и не продолжаемая до вычислимой функции, определённой на всём X. Утверждения (VI) и (II) в совокупности дают упоминаемый в ст. Алгоритм пример алгоритма ℑ с неразрешимой областью применимости.

Алгоритмические проблемы. Проблема построения алгоритма, обладающего теми или иными свойствами, называется алгоритмической проблемой (а. п.). Как правило, свойство искомого алгоритма формулируется в терминах свойств того соответствия, которое должно иметь место между исходными данными и результатами алгоритма. Важные примеры а. п.: проблема вычисления данной функции (требуется построить алгоритм, вычисляющий эту функцию): проблема разрешения данного множества (требуется построить алгоритм, разрешающий это множество относительно некоторого другого множества); проблема перечисления данного множества (требуется построить алгоритм, перечисляющий данное множество). Неразрешимость а. п. означает отсутствие соответствующего алгоритма; теоремы, устанавливающие неразрешимость таких проблем, относятся к числу наиболее важных теорем А. т.

Метрическая А. т. А. т. можно разделить на дескриптивную (качественную) и метрическую (количественную). Первая исследует алгоритмы с точки зрения устанавливаемого ими соответствия между исходными данными и результатами, к ней относятся, в частности, те алгоритмические проблемы, о которых говорилось в предыдущем разделе. Вторая исследует алгоритмы с точки зрения сложности как самих алгоритмов, так и задаваемых ими "вычислений", т. е. процессов последовательного преобразования конструктивных объектов. Важно подчеркнуть, что сложность алгоритмов и вычислений может определяться различными способами, причём может оказаться, что при одном способе А будет сложнее В, а при другом способе - наоборот. Чтобы говорить о сложности алгоритмов, надо сперва описать какой-либо точный язык для записи алгоритмов и затем под сложностью алгоритма понимать сложность его записи; сложность же записи можно определять различными способами (например, как число символов данного типа, участвующих в записи, или как набор таких чисел, вычисленных для разных типов символов). Чтобы говорить о сложности вычисления, надо уточнить, как именно вычисление представляется в виде цепочки сменяющих друг друга конструктивных объектов и что считается сложностью такой цепочки (только ли число членов в ней - "число шагов" вычисления или ещё учитывается "размер" этих членов и т. п.); в любом случае сложность вычисления зависит от исходного данного, с которого начинается вычисление, поэтому сложность вычисления есть функция, сопоставляющая с каждым объектом из области применимости алгоритма сложность соответствующей цепочки. Разработка методов оценки сложности алгоритмов и вычислений имеет важное теоретическое и практическое значение, однако в отличие от дескриптивной А. т., оформившейся в целостную математическую дисциплину, метрическая А. т. делает лишь первые шаги.

Приложения А. т. имеются во всех областях математики, в которых встречаются алгоритмические проблемы. Такие проблемы возникают в математической логике и теории моделей; для каждой теории формулируется проблема разрешения множества всех истинных или доказуемых предложений этой теории относительно множества всех её предложений (теории подразделяются на разрешимые и неразрешимые - в зависимости от разрешимости или неразрешимости указанной проблемы); в 1936 А. Чёрч установил неразрешимость проблемы разрешения для множества всех истинных предложений логики предикатов, дальнейшие важные результаты в этом направлении принадлежат А. Тарскому (См. Тарский), А. И. Мальцеву и др. Алгоритмические проблемы встречаются в алгебре (проблема тождества для полугрупп и, в частности, для групп: первые примеры полугрупп с неразрешимой проблемой тождества были найдены в 1947 независимо А. А. Марковым и Э. Л. Постом, а пример группы с неразрешимой проблемой тождества - в 1952 П. С. Новиковым); в топологии (проблема гомеоморфии, неразрешимость которой для важного класса случаев была доказана в 1958 А. А. Марковым); в теории чисел (остающаяся до сих пор открытой проблема разрешимости диофантовых уравнений) и др. разделах математики.

А. т. тесно связана с математической логикой, поскольку на понятие алгоритма опирается одно из центральных понятий математической логики - понятие исчисления (См. Исчисление) и потому, например, теорема К. Гёделя (См. Гёдель) о неполноте формальных систем может быть получена как следствие теорем А. т. Наконец, А. т. тесно связана с основаниями математики, в которых одно из центральных мест занимает проблема соотношения конструктивного и неконструктивного, в частности А. т. даёт аппарат, необходимый для разработки конструктивного направления (См. Конструктивное направление) в математике; в 1965 А. Н. Колмогоров предложил использовать А. т. для обоснования информации теории (См. Информации теория). А. т. образует теоретический фундамент для ряда вопросов вычислительной математики и тесно связана с кибернетикой, в которой важное место занимает изучение алгоритмов управления, в частности понятие алгоритма занимает центральное место в т. н. программированном обучении.

Лит.: Общие вопросы. Мальцев А. И., Алгоритмы и рекурсивные функции, М., 1965; Марков А. А., Теория алгорифмов, М. - Л., 1954 (Тр. Матем. института АН СССР, т. 42).

Отдельные вопросы. Колмогоров А. Н., Три подхода к определению понятия "количество информации", "Проблемы передачи информации", 1965, т. 1, в. 1; Ершов Ю. Л. [и др.], Элементарные теории, "Успехи математических наук", 1965, т. 20, в. 4; Марков А. А., О нормальных алгорифмах, связанных с вычислением булевых функций, "Известия АН СССР. Серия математическая", 1967, т. 31, в. 1; Трахтенброт Б. А., Сложность алгоритмов и вычислений, Новосиб., 1967.

В. А. Успенский.